The problem can be found at the following link: Question Link
The idea is to use a bitwise counting algorithm.
- We maintain an array
bits
of size 32 to store the count of set bits at each position for all the numbers in the array. - Then, we iterate through the array and update the
bits
array by counting the set bits for each number. - Finally, we go through the
bits
array and construct the result by adding the bits where the count is not a multiple of 3.
- Time Complexity:
O(N)
, where N is the length of the input array. - Auxiliary Space Complexity:
O(1)
(as we use only a constant 32 size vector).
class Solution {
public:
int singleElement(int arr[], int N) {
vector<int> bits(32, 0);
for (int i = 0; i < N; i++) {
for (int j = 0; j < 32; j++) {
bits[j] += arr[i] & 1;
arr[i] >>= 1;
}
}
int ans = 0;
for (int i = 0; i < 32; i++)
if (bits[i] % 3 != 0)
ans += 1 << i;
return ans;
}
};
For discussions, questions, or doubts related to this solution, please visit our discussion section. We welcome your input and aim to foster a collaborative learning environment.
If you find this solution helpful, consider supporting us by giving a ⭐ star to the getlost01/gfg-potd repository.